public class GraphColor {
    //用来标识地区的颜色
    static int[] flagLocalColor;
    //构造一张图
    static int[][] graph;
    //设置一个bool变量，用来记录是否已经找到一种方案
    static boolean check;
    //多少种颜色
    static int colorNum;

    //初始化图
    public static void addEdge(int v1, int v2) {
        graph[v1][v2] = graph[v2][v1] = 1;//1表示有边
    }

    public static void initGraph() {
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(0, 3);
        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(1, 4);
        addEdge(2, 3);
        addEdge(3, 4);
    }

    //localNum：多少个地区
    //colorNum：多少种颜色
    public static void permit(int localNum, int color) {
        //初始化
        flagLocalColor = new int[localNum];
        graph = new int[localNum][localNum];
        colorNum = color;
        initGraph();
        //开始深搜——回溯
        dfs(0, localNum);
    }

    //判断合法性
    public static boolean legal(int nowLocal) {
        //判断前面的地区是否满足要求
        for (int i = 0; i < nowLocal; i++) {
            if (graph[i][nowLocal] == 1
                    && flagLocalColor[i] == flagLocalColor[nowLocal])
                return false;
        }
        return true;
    }

    public static void output() {
        for (int i = 0; i < flagLocalColor.length; i++) {
            System.out.print(flagLocalColor[i] + " ");
        }
        System.out.println();
    }

    public static void dfs(int nowLocal, int localNum) {
        if(check){
            return;
        }
        //递归出口
        if (nowLocal == localNum) {
            output();
            check = true;
        } else {
            //是一棵多叉树
            for (int i = 0; i < colorNum; i++) {
                //先染色
                flagLocalColor[nowLocal] = i;
                //后判断，如果进不去dfs，证明没办法染色到最后一个地区，
                //最后for结束，回溯到上一层，相当于刚才的分支被剪枝了。
                if (legal(nowLocal)) {
                    /*
                    如果把flagLocalColor[nowLocal] = i放里面，会导致
                    nowLocal地区没被染色，从而导致判断方法legal的出错
                     */
                    dfs(nowLocal + 1, localNum);
                }
                //因为只找一个，所以不需要恢复现场
            }
        }
    }

    public static void main(String[] args) {
        permit(5,4);
    }

}
